The following prior art references are considered by applicants to be the most pertinent to the present invention:
[A] U.S. Pat. No. 4,888,779, granted Dec. 19, 1989, entitled "Matched Spectral Null Trellis Codes For Partial Response Channels."
[B] U.S. Pat. No. 5,257,272, granted Oct. 26, 1993, entitled "Time-Varying Modulo N Trellis Codes For Input Restricted Partial Response Channels."
[C] U.S. Pat. No. 5,280,489, granted Jan. 18, 1994, entitled "Time-Varying Viterbi Detector For Control Of Error Event Length."
[D] U.S. Pat. No. 5,327,440, granted Jul. 05, 1994, entitled "Systolic Architecture For Viterbi Detection Of DC-Free Sequences."
[E] Commonly assigned U.S. application Ser. No. 08/174,904, (Docket SA9-93-023), filed Dec. 24, 1993, entitled "Permuted Trellis Codes For Input Restricted Partial Response Channels."
[F] Commonly assigned U.S. application Ser. No. 08/242,942, (Docket SA9-94-012), filed May 16, 1994, entitled "Trellis Codes With Algebraic Constraints For Input Restricted Partial Response Channels."
Partial response channels of interest for data storage devices include those with channel polynomials of the form P(D)=(1-D.sup.n) or (1+D.sup.n), where n is a nonnegative integer. Channels with this form have a practical implementation advantage in that they can be de-interleaved into n separate (1-D) channels or n separate (1+D) channels, respectively. In Reference [A], coding and detection are accomplished by n-way interleaving of appropriate codes for the dicode channel, with polynomial (1-D), or n-way interleaving of appropriate codes for the so-called class-I partial-response channel, with polynomial (1+D).
Reference [A] discloses a method for increasing the reliability of partial response storage channels by increasing the minimum distance between coded output sequences using codes designed to match the spectral nulls in a channel partial response polynomial. The Viterbi detectors in Reference [A] reduce complexity by tracking only the spectral content of detected sequences.
The "minimum distance" of a particular detector trellis (sometimes referred to in the art as d.sup.2.sub.free) is defined as the minimum sum of the squared differences between sequences of noiseless sample values resulting from two distinct paths that diverge from a common state on the trellis and remerge to a common state. For partial response, maximum likelihood (PRML) detection, the minimum distance is 2; but the first-order matched-spectral null codes of Reference [A] increase the minimum distance to 4. In order to realize the benefits of increased minimum distance in a Viterbi detector with finite path memory, it is required that any pair of sequences consisting of a coded sequence and another detector trellis sequence accumulate the distance within a finite number of samples. If the code contains "quasicatastrophic" sequences, which are defined as sequences that are represented by more than one distinct path through the detector trellis, the minimum distance will not be accumulated in a finite number of samples, so it is necessary for the code to avoid such sequences. Reference [A] describes a method for eliminating quasicatastrophic sequences. However, in practice, reducing the required path memory to an appropriate length forces the encoder/decoder to become unacceptably complex.
Reference [B] describes a Viterbi detector which replicates a conventional trellis pattern for the desired channel N times. The N copies of the channel response trellis are interconnected in such a way that a preselected function associates each state in the trellis with a particular integer value modulo N. The number N is selected according to the channel detection and coding constraints so that diverging erroneous sequences of minimum distance lead to detector states which are distinct from the correct detector state. Only certain values of the preselected function tracked modulo N are allowed every m bits in order to increase the minimum distance between output sequences in the partial response channel and eliminate quasicatastrophic sequences. The codes described in Reference [B] do not match the spectral nulls in the polynomial for the channel.
Reference [C] describes a Viterbi detector based upon a time-varying trellis structure for detection of codes with spectral nulls or spectral-density nulls. The time-varying structure provides for reduced error-event length by eliminating paths corresponding to certain quasi-catastrophic sequences. The trellis is obtained by selective deletion of states and edges from the trellis that tracks the spectral content of the output sequences. However, while this selective deletion eliminates duplicate paths generating quasicatastrophic sequences, it also eliminates many paths generating sequences that might have been acceptable codewords and thereby reduces the achievable rate of codes supported by the modified trellis. Therefore, in order to maintain the desired high code rates, it was necessary to significantly increase the codeword block length or the number of trellis states, resulting in larger code and detector complexity.
Reference [D] describes sequences that are concatenated according to rules that depend upon the running digital sum (RDS) value of a sequence and that of its successor. The detector trellis structure combines subtrellises that track RDS or RDS modulo N, with reassignment of survivor metrics and survivor sequences at the subtrellis boundaries according to the sequence concatenation rules. The resulting detector trellis structure requires periodic permutation of states and hence is referred to as a "permuted" trellis code. The sequences and the concatenation rules are selected to realize coding gain, eliminate quasi-catastrophic sequences from the detector trellis, limit the complexity of the maximum-likelihood detector, and improve runlength constraints relative to earlier proposed methods.
Reference [E] describes sequences that satisfy an algebraic constraint on a predetermined algebraic attribute which identifies output sequences that differ from each other by a preselected error event. The detector tracks the algebraic attribute by iteratively computing from the symbols sequentially output from the detector trellis the value of the algebraic attribute at the end of each codeword. Violations of the algebraic constraint are flagged to detect the occurrence of the preselected error event. Allowable channel input sequences are constrained so that they will assume only a single value periodically in time. The detector trellis is made time-varying by removing from the trellis all output sequences that fail to satisfy the preselected algebraic constraint, thereby correcting said error event. The trellis is constructed to incorporate the current state of the partial response channel memory, the current state of the algebraic attribute, and, in an inner-coded system, the state of the inner code.
Reference [F] describes a systolic Viterbi detector trellis structure for MSN-coded and uncoded PRML channels. The architecture eliminates redundant detector calculations and incorporates modified butterfly trellis geometries and rotates state-metric assignments by one for simplifying the detector apparatus.
None of these references suggests (1) providing an encoder for a spectral-null code that partitions the set of sequences that are quasicatastrophic in a running-digital-sum (RDS) time-varying trellis structure by constraining codewords generated from an initial RDS value to assume prescribed subsets of allowable RDS values at both the codeword end and at least one prespecified interior location in the codeword; (2) providing a time-varying detector with a partitioned trellis structure which reflects the constraint on the encoded sequences by replicating certain states and edges in order to effect partitioning of the quasicatastrophic sequences; and (3) providing high rate MSN codes which further reduce the maximum length of error events at minimum distance and next-minimum distance, while retaining the beneficial features of the codes described in the above cited references.